package LeetCode刷题;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-11-12 14:54
 * @description: Functions of this class is
 **/
public class 二叉树路径总和I和II {
    /**
     *
     *！！！！！！！！！！在判断条件那里一定要判断*****是不是叶子******即左右节点都为空才可以
     *
     * 路径总和I:
     * class Solution {
     *     private boolean judge=false;
     *     public boolean hasPathSum(TreeNode root, int targetSum) {
     *         if(root!=null){
     *             judgeTree(root,targetSum);
     *         }
     *         return judge;
     *     }
     *     private void judgeTree(TreeNode root,int targetSum){
     *         if(root!=null){
     *             judgeTree(root.left,targetSum-root.val);
     *             if(root.left==null&&root.right==null&&targetSum-root.val==0){
     *                 judge=true;
     *                 return ;
     *             }
     *             judgeTree(root.right,targetSum-root.val);
     *         }
     *     }
     * }
     *
     *
     * 路径总和II：
     * class Solution {
     *     private boolean hasLeaf=false;
     *     public List<List<Integer>> pathSum(TreeNode root, int target) {
     *         List<List<Integer>> ans=new ArrayList();
     *         if(root!=null){
     *             List<Integer>sub=new ArrayList();
     *             if(root.left!=null||root.right!=null){
     *                 hasLeaf=true;
     *             }
     *             dfs(root,0,target,sub,ans);
     *         }
     *         return ans;
     *     }
     *     private void dfs(TreeNode cur,int tot,int target,List<Integer>sub,List<List<Integer>> ans){
     *         if(cur==null){
     *             return;
     *         }
     *         sub.add(cur.val);//把节点加入到子集集合中
     *         tot+=cur.val;
     *         if((cur.left==null&&cur.right==null)&&tot==target&&((sub.size()!=1&&hasLeaf)||(sub.size()==1&&!hasLeaf))){
     *             //如果有叶子节点存在的话，就不能只是根节点的值
     *             ans.add(new ArrayList<Integer>(sub));
     *         }
     *         dfs(cur.left,tot,target,sub,ans);//一直向左递归，
     *         //如果找不到的话就递归回溯
     *
     *         dfs(cur.right,tot,target,sub,ans);//然后向右递归
     *         //如果找不到的话就递归回溯
     *         tot-=cur.val;//tot减去当前节点的值
     *         sub.remove(sub.size()-1);//集合中去除
     *
     *     }
     * }
     */
}